package com.sheng.leetcode.year2023.month04.day20;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2023/04/20
 * <p>
 * 1187. 使数组严格递增<p>
 * <p>
 * 给你两个整数数组 arr1 和 arr2，返回使 arr1 严格递增所需要的最小「操作」数（可能为 0）。<p>
 * 每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引，分别为 i 和 j，<p>
 * 0 <= i < arr1.length 和 0 <= j < arr2.length，然后进行赋值运算 arr1[i] = arr2[j]。<p>
 * 如果无法让 arr1 严格递增，请返回 -1。<p>
 * <p>
 * 示例 1：<p>
 * 输入：arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]<p>
 * 输出：1<p>
 * 解释：用 2 来替换 5，之后 arr1 = [1, 2, 3, 6, 7]。<p>
 * <p>
 * 示例 2：<p>
 * 输入：arr1 = [1,5,3,6,7], arr2 = [4,3,1]<p>
 * 输出：2<p>
 * 解释：用 3 来替换 5，然后用 4 来替换 3，得到 arr1 = [1, 3, 4, 6, 7]。<p>
 * <p>
 * 示例 3：<p>
 * 输入：arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]<p>
 * 输出：-1<p>
 * 解释：无法使 arr1 严格递增。<p>
 * <p>
 * 提示：<p>
 * 1 <= arr1.length, arr2.length <= 2000<p>
 * 0 <= arr1[i], arr2[i] <= 10^9<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/make-array-strictly-increasing">1187. 使数组严格递增</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1187 {

    @Test
    public void test01() {
        int[] arr1 = {1, 5, 3, 6, 7}, arr2 = {1, 3, 2, 4};
//        int[] arr1 = {1, 5, 3, 6, 7}, arr2 = {4, 3, 1};
//        int[] arr1 = {1, 5, 3, 6, 7}, arr2 = {1, 6, 3, 3};
        System.out.println(new Solution().makeArrayIncreasing(arr1, arr2));
    }
}

/**
 * 我们定义 f[i] 表示将 arr1[0,..,i] 转换为严格递增数组，且 arr1[i] 不替换的最小操作数。
 * 因此，我们在arr1 设置首尾两个哨兵 −∞ 和 ∞。最后一个数一定是不替换，因此f[n−1] 即为答案。
 * 我们初始化 f[0]=0，其余f[i]=∞。接下来我们对数组arr2 进行排序并去重，方便进行二分查找。
 * 对于 i=1,..,n−1，我们考虑arr1[i−1] 是否替换。
 * 如果 arr1[i−1]<arr1[i]，那么f[i] 可以从f[i−1] 转移而来，即f[i]=f[i−1]。
 * 然后，我们考虑arr[i−1] 替换的情况，显然arr[i−1] 应该替换成一个尽可能大的、且比arr[i] 小的数字，
 * 我们在数组arr2 中进行二分查找，找到第一个大于等于arr[i] 的下标j。
 * 然后我们在k∈[1,min(i−1,j)] 的范围内枚举替换的个数，如果满足arr[i−k−1]<arr2[j−k]，那么f[i] 可以从f[i−k−1] 转移而来，
 * 即f[i]=min(f[i],f[i−k−1]+k)。最后，如果f[n−1]≥∞，说明无法转换为严格递增数组，返回−1，否则返回f[n−1]。
 * <p>
 * 作者：lcbin
 * 链接：https://leetcode.cn/problems/make-array-strictly-increasing/solution/python3javacgotypescript-yi-ti-yi-jie-do-j5ef/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
class Solution {
    public int makeArrayIncreasing(int[] arr1, int[] arr2) {
        // 排序
        Arrays.sort(arr2);
        int m = 0;
        for (int x : arr2) {
            if (m == 0 || x != arr2[m - 1]) {
                arr2[m++] = x;
            }
        }
        final int inf = 1 << 30;
        int[] arr = new int[arr1.length + 2];
        arr[0] = -inf;
        arr[arr.length - 1] = inf;
        System.arraycopy(arr1, 0, arr, 1, arr1.length);
        int[] f = new int[arr.length];
        Arrays.fill(f, inf);
        f[0] = 0;
        for (int i = 1; i < arr.length; ++i) {
            if (arr[i - 1] < arr[i]) {
                f[i] = f[i - 1];
            }
            int j = search(arr2, arr[i], m);
            for (int k = 1; k <= Math.min(i - 1, j); ++k) {
                if (arr[i - k - 1] < arr2[j - k]) {
                    f[i] = Math.min(f[i], f[i - k - 1] + k);
                }
            }
        }
        return f[arr.length - 1] >= inf ? -1 : f[arr.length - 1];
    }

    private int search(int[] nums, int x, int n) {
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}
